package cs275.ants.graph.base;

/**
 * Undirected graph implemented using incidence list (extension of adjacency list with edge cost) 
 * 
 * expect sparse graph. for other purpose, use an adjacency matrix implementation
 */


import java.io.Serializable;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

import org.lwjgl.util.Point;

import com.google.common.collect.Maps;
import com.google.common.collect.Sets;

public class Graph implements Serializable {

	protected HashMap<Point, GraphVertex> vertices;
	public Graph() {
		this.vertices = Maps.newHashMap();
	}
	
	/**
	 * Serialization ID
	 */
	private static final long serialVersionUID = 1L;
	
	private HashMap<GraphVertex, HashSet<GraphEdge>> incidenceMap =
		Maps.<GraphVertex, HashSet<GraphEdge>>newLinkedHashMap();
	
	/**
	 * Add a vertex to the map
	 * @param vertex
	 * @return true if success, false otherwise
	 */
	public boolean addVertex(GraphVertex vertex) {
		vertices.put(vertex.getCoordinates(), vertex);
		if (incidenceMap.containsKey(vertex)) {
			return false;
		}	
		
		HashSet<GraphEdge> edges = Sets.<GraphEdge>newLinkedHashSet();
		incidenceMap.put(vertex, edges);
		return true;
	}
	
	/**
	 * Utility method for adding many vertices.
	 */
	public void addVertices(GraphVertex... vertices) {
		for(GraphVertex vertex : vertices) {
			addVertex(vertex);
		}
	}
	
	/**
	 * Remove a vertex from the graph 
	 * @param vertex
	 * @return true if success, false if vertex not in graph or fail
	 */
	public boolean removeVertex(GraphVertex vertex) { 
		if (!incidenceMap.containsKey(vertex)) { 
			return false; 
		} else { 
			incidenceMap.remove(vertex);
			return true;
		}
	}
	
	/**
	 * Get all vertices in the graph
	 * @return all vertices in a Set<GraphVertex> 
	 */
	public Set<GraphVertex> getAllVertices() {
		return incidenceMap.keySet();
	}
	
	public Set<GraphEdge> getAllEdges() {
		Collection<HashSet<GraphEdge>> hashSets = incidenceMap.values();
		Set<GraphEdge> allEdges = Sets.<GraphEdge>newHashSet();
		for(HashSet<GraphEdge> set : hashSets) {
			allEdges = Sets.union(allEdges, set);
		}
		return allEdges;
	}
	
	public GraphEdge addEdge(GraphEdge newEdge) {
		HashSet<GraphEdge> edgeSet1 = incidenceMap.get(newEdge.getNode1());
		if (edgeSet1 == null) {
			return null;
		}
		if (!edgeSet1.contains(newEdge)) { 
			edgeSet1.add(newEdge);
		}

		HashSet<GraphEdge> edgeSet2 = incidenceMap.get(newEdge.getNode2());
		if (edgeSet2 == null) {
			return null;
		}
		if (!edgeSet2.contains(newEdge)) { 
			edgeSet2.add(newEdge);
		}
		
		return newEdge;
	}
	
	public HashSet<GraphEdge> addEdges(GraphEdge... edges) {
		HashSet<GraphEdge> addedEdges = Sets.newLinkedHashSet();
		for(GraphEdge edge : edges) {
			addedEdges.add(addEdge(edge));
		}
		return addedEdges;
	}
	
	/**
	 * Remove an edge from the graph
	 * @param edge
	 * @return true if success, false if edge not exists or fail
	 */
	public boolean removeEdge(GraphEdge edge) {
		
		HashSet<GraphEdge> edgeSet = incidenceMap.get(edge.getNode1());
		if (edgeSet == null) { 
			return false;
		} else {
			if (!edgeSet.remove(edge)) { 
				return false;
			}
		}
		
		
		HashSet<GraphEdge> edgeSet2 = incidenceMap.get(edge.getNode2());
		if (edgeSet2 == null) { 
			return false;
		} else { 
			if (!edgeSet2.remove(edge)) {
				return false;
			}
		}
		
		return true;
	}
	
	/**
	 * Get edges connected to a given vertex
	 * @param vertex
	 * @return all connected edges in HashSet<GraphEdge>, null if vertex not exists
	 */
	public HashSet<GraphEdge> getEdgesByVertex(GraphVertex vertex) {
		return incidenceMap.get(vertex);
	}

	/**
	 * Same as {@link #getEdgesByVertex(GraphVertex)} but strips the edge
	 * information of current edge, cost, etc.
	 */
	public HashSet<GraphVertex> getNeighborsByVertex(GraphVertex vertex) {
		HashSet<GraphVertex> neighbors = Sets.newLinkedHashSet();
		HashSet<GraphEdge> edges = getEdgesByVertex(vertex);
		for(GraphEdge edge : edges) {
			if(!edge.getNode1().equals(vertex)) {
				neighbors.add(edge.getNode1());
			} else {
				neighbors.add(edge.getNode2());
			}
		}
		return neighbors;
	}

	public GraphVertex getVertex(int row, int col) {
		return vertices.get(new Point(col, row));
	}
}
